#define DEBUG
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn=15, mods=1000000007;

int main() {
  freopen("winner.in", "r", stdin);
  freopen("winner.out", "w", stdout);

  static bool map[maxn+1][maxn+1];
  int n, m, id;
  scanf("%d %d %d", &n, &m, &id);
  for (int i=1; i<=m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    map[a][b] = map[b][a] = true;
  }

  static ll f[1<<maxn], g[1<<maxn], h[1<<maxn];
  static int gra[1<<maxn];
  h[0] = 1;
  for (int i=1; i<(1<<n); i++) {
    for (int j=1; j<=n; j++) {
      if ((i>>(j-1))&1) {
        gra[i] = gra[i-(1<<(j-1))];
        h[i] = h[i-(1<<(j-1))];
        for (int k=1; k<=n; k++) {
          gra[i] |= (map[j][k]<<(k-1));
          if (((i>>(k-1))&1) && map[j][k]) {
            h[i] = h[i]*2%mods;
          }
        }
        break;
      }
    }
  }

  f[1] = 1, g[2]=1;
  for (int i=3; i<(1<<n); i++) {
    if (i&1) {
      f[i] = h[i];
      for (int j=(i-1)&i; j; j=(j-1)&i) {
        f[i] = (f[i]+mods-f[j]*h[i-j]%mods)%mods;
      }
    }
    if (i&2) {
      g[i] = h[i];
      for (int j=(i-1)&i; j; j=(j-1)&i) {
        g[i] = (g[i]+mods-g[j]*h[i-j]%mods)%mods;
      }
    }
  }

  ll ans = h[(1<<n)-1];
  for (int i=1; i<(1<<n); i++) {
    if (i&1) {
      int t=(1<<n)-1-i;
      for (int j=t; j; j=(j-1)&t) {
        if (!(gra[i]&j)) {
          ans = (ans+mods-f[i]*g[j]%mods*h[(1<<n)-1-i-j]%mods)%mods;
        }
      }
    }
  }
  printf("%lld", ans);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
